package practices;

import sun.tools.tree.PostIncExpression;

import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class BinaryTree {
    String root;
    BinaryTree left, right;

    BinaryTree(String root) {
        this(root, null, null);
    }

    public BinaryTree(String root, BinaryTree left, BinaryTree right) {
        this.root = root;
        this.left = left;
        this.right = right;
    }

    void preVisit() {   //先序遍历：根节点-左节点-右节点
        System.out.print(root + " ");
        if (left != null) {
            left.preVisit();
        }
        if (right != null) {
            right.preVisit();
        }
    }

    void postVisit() {  //后序遍历：左节点-右节点-根节点
        if (left != null) {
            left.postVisit();
        }
        if (right != null) {
            right.postVisit();
        }
        System.out.print(root + " ");
    }

    void midVisit() {   //中序遍历：左节点-根节点-右节点
        if (left != null) {
            left.midVisit();
        }
        System.out.print(root + " ");
        if (right != null) {
            right.midVisit();
        }
    }

    /**
     * 根据后缀表达式是生成运算二叉树
     *
     * @param exp
     */
    public static BinaryTree createBinaryTree(List<String> exp) {
        Stack<BinaryTree> S = new Stack<>();
        for (String tok : exp) {
            if (PostExpression.isNumber(tok)) {
                BinaryTree tree = new BinaryTree(tok);
                S.push(tree);
            } else {
                BinaryTree right = S.peek();
                S.pop();
                BinaryTree left = S.peek();
                S.pop();
                BinaryTree tree = new BinaryTree(tok, left, right);
                S.push(tree);
            }
        }
        return S.peek();
    }

    public static void main(String[] args) {
//        BinaryTree left = new BinaryTree("1");
//        BinaryTree right = new BinaryTree("3");
//        BinaryTree exp = new BinaryTree("+", left, right);
//        System.out.println("先序遍历");
//        exp.preVisit();
//        System.out.println("\n中序遍历");
//        exp.midVisit();
//        System.out.println("\n后序遍历");
//        exp.postVisit();
        BinaryTree exp2 = BinaryTree.createBinaryTree(Arrays.asList("1 2 + 3 4 + *".split("\\s+")));
        exp2.midVisit();
    }
}
